package xyf.p08.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: P0046_Permute
 * Description:
 * Author: xyf
 * Date: 9/8/22 4:44 PM
 * Version: 1.0
 **/
public class P0046_Permute
{
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums)
    {
        dfs(nums, 0, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int curIndex, List<Integer> path)
    {
        if (curIndex == nums.length)
        {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++)
        {
            if (path.contains(nums[i]))
            {
                continue;
            }

            path.add(nums[i]);

            dfs(nums, curIndex + 1, path);

            path.remove(path.size() - 1);
        }
    }
}